<?php
/**
 * User: helloJiu
 * Date: 2021/11/4
 * Time: 10:07
 */

namespace App\Algorithm\DP;


class CoinChangeII
{
    /**
     * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
     *
     * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
     *
     * 假设每一种面额的硬币有无限个。 
     *
     * 题目数据保证结果符合 32 位带符号整数
     *
     * 输入：amount = 5, coins = [1, 2, 5]
     * 输出：4
     * 解释：有四种方式可以凑成总金额：
     * 5=5
     * 5=2+2+1
     * 5=2+1+1+1
     * 5=1+1+1+1+1
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/coin-change-2
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param Integer $amount
     * @param Integer[] $coins
     * @return Integer
     */
    function change($amount, $coins)
    {
        $dp = [];
        // $dp[$m] 表示凑够$m金额有$dp[$m]中方式
        // 转移方程   $dp[$m] = $dp[$m-$coin] + $dp[$m]
        for ($m = 0; $m <= $amount; $m++) {
            $dp[$m] = 0;
        }

        // 凑够0 可以一个硬币都不选
        $dp[0] = 1;

        foreach ($coins as $coin) {
            for ($m = 1; $m <= $amount; $m++) {
                if ($m >= $coin) {
                    $dp[$m] = $dp[$m] + $dp[$m - $coin];
                }
            }
        }
        return $dp[$amount];
    }
}